package solutions.face.easy;

import solutions.lib.BaseSolution;
import solutions.lib.TreeNode;

/**
 * @author lizhidong
 * <a href="https://leetcode-cn.com/problems/binode-lcci/">17_12.BiNode</a>
 */
public class Solution17_12 extends BaseSolution {

    TreeNode minNode;

    public TreeNode convertBiNode(TreeNode root) {
        if (root == null) {
            return null;
        }
        //遍历右子树
        convertBiNode(root.right);
        //遍历根节点
        root.right = minNode;
        minNode = root;
        //遍历左子树
        convertBiNode(root.left);
        //置空左指针
        root.left = null;
        return minNode;
    }

    public static void main(String[] args) {
        Solution17_12 solution = new Solution17_12();
        TreeNode origin = new TreeNode(4,
                new TreeNode(2,
                        new TreeNode(1,
                                new TreeNode(0),
                                null
                        ),
                        new TreeNode(3)
                ),
                new TreeNode(5,
                        null,
                        new TreeNode(6)
                )
        );
        System.out.println(origin);
        TreeNode node = solution.convertBiNode(origin);
        System.out.println(node.toString());
    }
}